package 题目集.滑动窗口.ch02_不定长窗口;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/
 */
public class ch02_无重复最长子串 {
    /**
     * ch01:无重复字符的最长子串
     */
    @Test
    public void test01(){
        System.out.println(lengthOfLongestSubstring("abba"));
    }

    /**
     * ch01:无重复字符的最长子串
     * 思路：哈希表+滑动窗口实现
     *      1.准备一个哈希表，存放每个字符最后出现的位置，准备一个滑动窗口存放不相同的子串
     *      2.依次向哈希表中添加字符
     *          当字符出现过，判断该窗口内字符是否为最长（更新max），将窗口缩小至该字符上一次出现的下一个位置，将被丢掉的部分从map中移除，窗口向右扩容
     *          当字符未出现时，放入map中，窗口向右扩容
     */
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        Map<Character,Integer> map=new HashMap<>();
        int max=0;
        int i = 0,j=0;
        while (j < chars.length) {
            if (map.containsKey(chars[j])) {
                max=Math.max(max,j-i);
                int l=map.get(chars[j])+1;
                while (i<l){
                    map.remove(chars[i]);
                    i++;
                }
            }
            map.put(chars[j],j);
            j++;
        }
        max=Math.max(max,j-i);
        return max;
    }

}
